1. Field of the Invention
The present invention relates to a circuit for calculating an error position polynomial in an error correcting system using a Reed-Solomon code, and more particularly, to a circuit which can rapidly calculate an error position polynomial by using the Berlekamp-Massey iterative algorithm.
2. Description of the Related Art
In digital communication and storage systems, a Reed-Solomon (hereinafter, referred to as the RS) code for controlling an error has widely been used. In data coded to the RS code, an error is frequently generated during data transmission or reproduction. Since incorrect data is received due to this error, the data coded into the RS code needs to be error-corrected by RS decoding. In this RS decoding process, it is necessary to calculate an error position polynomial having an error position as a root. Examples of such error position polynomial calculation are described in papers, R. E. Blahut, "Theory and Practice of Error Control Code", Addison-Wesley, 1983, and J. L. Massey, "Shift Register Synthesis and BCH Decoding" IEEE Transactions on Information Theory, Vol. IT-15, pp. 122-127, January, 1969. As a circuit using the Berlekamp-Massey algorithm (BMA) to calculate the error position, there is an example using a linear feedback shift register (LFSR) published by Massey, 1965. A discrepancy is calculated from a syndrome and an error position polynomial. If the discrepancy is 0, the previous error position polynomial is used. If it is not 0, the error position polynomial is again calculated. In order to again calculate the error position polynomial, a correction polynomial is given. That is, a new error position polynomial is calculated by using the correcting polynomial and the discrepancy. However, since such a circuit has a parallel structure, many multipliers are required to calculate the error position polynomial, and thus, the size of the circuit is increased. Moreover, since there is a long delay time in a circuit for calculating the discrepancy and a circuit for calculating the error position polynomial using the discrepancy, it is difficult to apply such a conventional circuit to a digital communication system which pursues a high-speed operation or to a storage system which has high storage capacity and requires high-speed access.